package lhc.alg.top100;

/**
 * description: https://leetcode.cn/problems/odd-even-linked-list/
 * 奇偶链表 用迭代的方式 搞成两个链表一个奇 一个偶 再给他两连起来
 *
 * author: hongchen.liao
 * date:  2022/8/10
 */
public class _328_Odd_Even_Linked_List {


    //Definition for singly-linked list.
    public class ListNode {
        int val;
        ListNode next;
        ListNode() {}
        ListNode(int val) { this.val = val; }
        ListNode(int val, ListNode next) { this.val = val; this.next = next; }
    }

    class Solution {
        public ListNode oddEvenList(ListNode head) {
            if(head == null) return head;
            ListNode evenHead = head.next;
            ListNode odd = head, even = evenHead;
            while(even != null && even.next != null){
                odd.next = even.next;
                odd = odd.next;
                even.next = odd.next;
                even = even.next;
            }
            odd.next = evenHead;
            return head;
        }
    }

}
